package cg.studio.algorithm.permutation;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Set;
import java.util.SortedMap;

/**
 * Generate the permutation calculate the position of each character
 * how many 'a' in first column equals to how many words when get rid of a
 * 
 * abc:   ???
 *   a      a b      a b c 
 *   a      a c      a c b 
 *   b  ==> b a  ==> b a c  
 *   b      b c      b c a                    
 *   c      c a      c a b                     
 *   c      c b      c b a                   
 *            
 * @author Bright Chen
 *
 */
public class CalculatedPermutator implements Permutator
{
  public List< char[] > permutate( String str )
  {
    if( str == null || str.isEmpty() )
      return Collections.emptyList();

    str = str.toUpperCase();
    final int strSize = str.length();  
    
    SortedMap< Character, Integer > charToCountMap = PermutationUtils.getCharToCountMap( str );
    int totalStringCount = calculatePermutationCount( charToCountMap );
    char[][] charPermutations = new char[totalStringCount][strSize];
    
    //
    Set< Character > keys = charToCountMap.keySet();
    Character[] keyArray = keys.toArray( new Character[0] );
    
    //calculate column by column
    for( int columnIndex = 0; columnIndex < strSize; ++columnIndex )
    {
      
      for( int rowIndex = 0; rowIndex < totalStringCount;  )
      {
        for( int charIndex = 0; charIndex < keyArray.length && rowIndex < totalStringCount; ++charIndex )
        {
          getRemainedCharToCountMap( charToCountMap, charPermutations, rowIndex, columnIndex );
          
          char theKey = keyArray[ charIndex ];
          if( charToCountMap.get( theKey ) == null || charToCountMap.get( theKey ) == 0 )
          {
            recoverCharToCountMap( charToCountMap, charPermutations, rowIndex, columnIndex );
            continue;
          }
  
          //calculate how many permutations for all chars except <theKey>
          PermutationUtils.decreaseCharCount( charToCountMap, theKey );
          int otherPermutations = calculatePermutationCount( charToCountMap );
          int startRowIndex = rowIndex;
          for( int rowOfThisChar = 0; rowOfThisChar < otherPermutations; ++rowOfThisChar, ++rowIndex )
          {
            //it is sure that the previous chars in these rows( rows for <theKey>) are same.
            charPermutations[rowIndex][columnIndex] = theKey;
          }
          
          //recover the map
          PermutationUtils.increaseCharCount( charToCountMap, theKey );
          //the rowIndex probably out of range here.
          recoverCharToCountMap( charToCountMap, charPermutations, startRowIndex, columnIndex );
        }
      }
    }
    
    return Arrays.asList( charPermutations );
  }

  /**
   * remove the chars/count which already Permutated 
   * @param charToCountMap
   * @param charPermutations
   * @param rowIndex
   * @param charCountInRow
   * @return
   */
  protected SortedMap< Character, Integer > getRemainedCharToCountMap( SortedMap< Character, Integer > charToCountMap, 
                                                                       char[][] charPermutations,
                                                                       int rowIndex, int charCountInRow )
  {
    char[] charsInRow = charPermutations[rowIndex];
    for( int index = 0; index < charCountInRow; ++index )
    {
      PermutationUtils.decreaseCharCount( charToCountMap, charsInRow[ index ] );
    }
    return charToCountMap;
  }
  
  /**
   * recover the <charToCountMap> for use next
   * @param charToCountMap
   * @param charPermutations
   * @param rowIndex
   * @param charCountInRow
   * @return
   */
  protected SortedMap< Character, Integer > recoverCharToCountMap( SortedMap< Character, Integer > charToCountMap, 
                                                                   char[][] charPermutations,
                                                                   int rowIndex, int charCountInRow )
  {
    char[] charsInRow = charPermutations[rowIndex];
    for( int index = 0; index < charCountInRow; ++index )
    {
      PermutationUtils.increaseCharCount( charToCountMap, charsInRow[ index ] );
    }
    return charToCountMap;
  }
  

  // let's say AAABBC, when insert second A, divide two; insert 3rd A, divide three; etc
  /*************
  private int getNumberOfPermuation( final int[] charToCountMap )
  {
    int number = 1;
    int totalSeq = 0;
    for( int index = 0; index < 'Z'-'A'; ++index )
    {
      int count = charToCountMap[ index ];
      if( count == 0 )
        continue;
      for( int i=1; i<=count; ++i )
      {
        number *= ++totalSeq;
        number /= i;
      }
    }
    return number;
  }
  /*************/
  
  /**
   * calculate how many permutation for <charToCountMap>
   * @param charToCountMap
   * @return
   */
  private int calculatePermutationCount( SortedMap< Character, Integer > charToCountMap  )
  {
    return calculatePermutationCount( charToCountMap, null, 0 );
  }

  /**
   * calculate how many permutation for <charToCountMap>, which start with <startIndexOfChar> of <startChar>
   * @param charToCountMap
   * @param startChar
   * @param startIndexOfChar
   * @return
   */
  private int calculatePermutationCount( SortedMap< Character, Integer > charToCountMap, Character startChar, int startIndexOfChar  )
  {
    //the keys are sorted
    Set<Character> keys = charToCountMap.keySet();
    int permutationCount = 1;
    int totalCharCount = 1;
    for( Character key : keys )
    {
      if( startChar != null && key.charValue() < startChar.charValue() )
        continue;
      
      int sameCharCount = charToCountMap.get( key );
      if( startChar == null || key.charValue() > startChar.charValue() )
      {
        startIndexOfChar = 0; // the scenario of key>startChar can be treat as a special case of key==startChar 
      }
      for( int index = startIndexOfChar; index < sameCharCount; ++index, ++totalCharCount )
      {
        permutationCount *= totalCharCount;
        permutationCount /= ( index - startIndexOfChar + 1 );
      }
    }
    return permutationCount;
  }

}
